package com.jinyang.jetpackdemo

/**
 * @Author:         LiuJinYang
 * @CreateDate:     2022/1/6
 * @Description:  匿名递归函数，Y组合子(The Y combinator)
 */
typealias G<T, R> = (T) -> R

//public interface Function1<in P1, out R> : Function<R> {
//    public operator fun invoke(p1: P1): R
//}

interface F<T, R> : Function1<F<T, R>, G<T, R>>

fun <T, R> f(block: (F<T, R>) -> G<T, R>) = object : F<T, R> {
    //调用函数自身`block(f)` like as `f(f)`
    override fun invoke(f: F<T, R>) = block(f)
}

typealias E<T, R> = Function1<G<T, R>, G<T, R>>

//Y 组合子函数:
fun <T, R> Y(e: E<T, R>) = { f: F<T, R> -> f(f) }(f { f ->
    e { x -> f(f)(x) }
})
//fun <T, R> Y(e: E<T, R>): G<T, R> {
//    val p1 = f<T, R> { f ->
//        e { x -> f(f)(x) }
//    }
//    return p1(p1)
//}

//Y 组合子实现阶乘与斐波那契数列:

val factorial: (Int) -> Int = Y { f ->
    { x ->
        if (x == 0) 1 else x * f(x - 1)
    }
}

val fib: (Int) -> Int = Y { f ->
    { x ->
        if (x == 1 || x == 2) 1 else f(x - 1) + f(x - 2)
    }
}

fun main() {
    println(fib(10)) // 55
    println(factorial(10)) // 3628800
}
